﻿public partial class Solution
{
    public int MySqrt(int x)
    {
        int result = 0;
        if (x <= 1)
        {
            result = x;
        }
        else
        if (x <= 3)
        {
            result = 1;
        }
        else
        {
            int lp = 2;
            int rp = x / 2;
            while (lp <= rp)
            {
                int mid = (lp + rp) / 2;
                // 需要用long类型来存储mid*mid的结果，避免溢出
                long temp = Convert.ToInt64(mid) * Convert.ToInt64(mid);
                if (temp <= x)
                {
                    result = mid;
                    lp = mid + 1;
                }
                else
                {
                    rp = mid - 1;
                }
            }
        }
        return result;
    }
}